# -*- coding: utf-8 -*-
# @Time : 2023/10/23 20:44
# @Author : ZH
# @File : 22.py
# @Software: PyCharm
from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return
            if left < n:
                S.append('(')
                backtrack(S, left+1, right)
                S.pop()
            if right < left:
                S.append(')')
                backtrack(S, left, right+1)
                S.pop()

        backtrack([], 0, 0)
        return ans


if __name__ == '__main__':
    so = Solution()
    so.generateParenthesis(n=3)



